package com.gxc.integer;

/**
 * 552. 学生出勤记录 II

 * 可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。
 * 记录中只含下面三种字符：
 * 'A'：Absent，缺勤
 * 'L'：Late，迟到
 * 'P'：Present，到场
 * 如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
 *
 * 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
 * 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。
 *
 * 给你一个整数 n ，表示出勤记录的长度（次数）。
 * 请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。
 * 答案可能很大，所以返回对 109 + 7 取余 的结果。
 */
public class CheckRecord {

    public static void main(String[] args) {
        System.out.println(handle(2));
        System.out.println(handle(1));
        System.out.println(handle(10101));

        System.out.println(handle2(2));
        System.out.println(handle2(1));
        System.out.println(handle2(10101));
    }

    /**
     * dp[i][j][k] i长度的字符有 j 个A的数量， k 个连续L的数量
     * @param n
     * @return
     */
    public static int handle(int n) {
        int mod = 1000000000 + 7;

        int[][][] dp = new int[n + 1][2][3]; // 长度，A 的数量，结尾连续 L 的数量
        dp[0][0][0] = 1;

        for (int i = 1; i <= n; i++) {
            //尝试添加A   ..P.A   ..LA  ..LLA
            //A添加后  A的个数+1  重置连续L的个数
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k])%mod;
            }
            //尝试添加L   ..P.L   ..A.L  ..LL
            //P添加后  连续L的个数+1  A的数量不变
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 1; k++) {
                    dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][j][k])%mod;
                }
            }
            //尝试添加P   ..P.P   ..A.P  ..LP   ..LLP
            //P添加后重置连续L的个数 A的数量不变
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][k])%mod;
                }
            }
        }

        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[n][j][k])%mod;
            }
        }
        return sum;
    }

    /**
     * dp[i][j][k]   = dp[i-1][][]  + dp[i-1][][]
     * dp[i][j][k] i长度的字符有 j 个A的数量， k 个连续L的数量
     * 空间优化  dp[j][k]
     * @param n
     * @return
     */
    public static int handle2(int n) {
        int mod = 1000000000 + 7;

        int[][] dp = new int[2][3]; // 长度，A 的数量，结尾连续 L 的数量
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            int[][] dpNew = new int[2][3];
            //尝试添加A   ..P.A   ..LA  ..LLA
            //A添加后  A的个数+1  重置连续L的个数
            for (int k = 0; k <= 2; k++) {
                dpNew[1][0] = (dpNew[1][0] + dp[0][k])%mod;
            }
            //尝试添加L   ..P.L   ..A.L  ..LL
            //P添加后  连续L的个数+1  A的数量不变
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 1; k++) {
                    dpNew[j][k+1] = (dpNew[j][k+1] + dp[j][k])%mod;
                }
            }
            //尝试添加P   ..P.P   ..A.P  ..LP   ..LLP
            //P添加后重置连续L的个数 A的数量不变
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dpNew[j][0] = (dpNew[j][0] + dp[j][k])%mod;
                }
            }
            dp = dpNew;
        }

        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[j][k])%mod;
            }
        }
        return sum;
    }

    /**
     * 矩阵快速幂
     */

}
